Search results for "Parity function"
showing 4 items of 4 documents
Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms
2005
The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.
Exact quantum algorithms have advantage for almost all Boolean functions
2014
It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.
Quantum Query Algorithms for Conjunctions
2010
Every Boolean function can be presented as a logical formula in conjunctive normal form. Fast algorithm for conjunction plays significant role in overall algorithm for computing arbitrary Boolean function. First, we present a quantum query algorithm for conjunction of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p = 4/5, that improves the previous result. Then, we present the main result - generalization of our approach to design efficient quantum algorithms for computing conjunction of two Boolean functions. Finally, we demonstrate another kind of an algorithm for conjunction of two bits, that has a correct answer probability p = 9/10. Th…
High precision quantum query algorithm for computing AND-based boolean functions
2010
Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. The complexity of the algorithm is measured by the number of queries on the worst-case input. In this paper we consider computing AND Boolean function. First, we present a quantum algorithm for AND of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p=4/5, that improves previous results. The main result is generalization of our approach to design efficient quantum algorithms for computing composite function AND(f1,f2) where fi…